#include "BreadthFirstSearch.h"

namespace zbp
{
	using namespace boost;

	double breadth_search_first_SimpleGraph_test(zbp::SimpleGraph g, bool display, int s)
	{		
		clock_t ticks = clock();

		for (int i = 0; i < g.adjacency_list.get_nodes_count(); i++)
		{
			vector<bool> d;
			g.breadth_first_search(i,d);
		}

		ticks = clock() - ticks;
		double msec = (double)ticks / CLOCKS_PER_SEC * 1000;

		if (display)
		{
			cout << "SimpleGraph class: breath first search " << s << endl << endl;	
			/*for (int i = 0; i < d.size(); i++)
			{
				std::cout << d[i] << " ";
			}*/
			cout << "Time in ms: " << msec << endl << endl;
		}

	return msec;
	}

	struct EdgeProperties {
	  int weight;
	};
	template < typename TimeMap > class bfs_time_visitor:public default_bfs_visitor {
	  typedef typename property_traits < TimeMap >::value_type T;
	public:
	  bfs_time_visitor(TimeMap tmap, T & t):m_timemap(tmap), m_time(t) { }
	  template < typename Vertex, typename Graph >
		void discover_vertex(Vertex u, const Graph & g) const
	  {
		put(m_timemap, u, m_time++);
	  }
	  TimeMap m_timemap;
	  T & m_time;
	};
	double breadth_search_first_boost_test(int source_vertex, BoostEdge* edge_array, int* weights, int nodes_count, int edges_count, bool display)
	{
		typedef adjacency_list < vecS, vecS, directedS,
		no_property, EdgeProperties> graph_t;
			
	#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300	
		graph_t g(nodes_count);
		for (std::size_t j = 0; j < num_arcs; ++j)
			add_edge(edge_array[j].first, edge_array[j].second, g);
	#else
		typedef graph_traits<graph_t>::vertices_size_type v_size_t;
		graph_t g(edge_array, edge_array + edges_count, v_size_t(nodes_count));
	#endif

	  // Typedefs
	  typedef graph_traits < graph_t >::vertex_descriptor Vertex;
	  typedef graph_traits < graph_t >::vertices_size_type Size;
	  typedef Size* Iiter;

	  // a vector to hold the discover time property for each vertex
	  std::vector < Size > dtime(num_vertices(g));
	   
	  Size time = 0;
	  bfs_time_visitor < Size * >vis(&dtime[0], time);

	  clock_t ticks = clock();

	  for (int i = 0 ; i < nodes_count; i++)
	  {
		breadth_first_search(g, vertex(i,g), visitor(vis));	  
	  }

	  ticks = clock() - ticks;	
	  double msec = (double)ticks / CLOCKS_PER_SEC * 1000;

	  // Use std::sort to order the vertices by their discover time
	  std::vector<graph_traits<graph_t>::vertices_size_type > discover_order(nodes_count);
	  integer_range < int >range(0, nodes_count);
	  std::copy(range.begin(), range.end(), discover_order.begin());
	  std::sort(discover_order.begin(), discover_order.end(),
				indirect_cmp < Iiter, std::less < Size > >(&dtime[0]));

	  if (display)
	  {
		  std::cout << "order of discovery: ";
		  for (int i = 0; i < nodes_count; i++)
			std::cout << discover_order[i] << " ";
		  std::cout << std::endl;
		  cout << "Time in ms: " << msec << endl << endl;
	  }

	  return msec;
	}

	void breath_search_first_tests_run(zbp::SimpleGraph simple_graph, zbp::BoostEdge* boost_edges, int* boost_weights, int nodes_count, int edges_count, int s)
	{
		breadth_search_first_boost_test(s, boost_edges, boost_weights, nodes_count, edges_count, true);
		breadth_search_first_SimpleGraph_test(simple_graph, true, s);
	}
}